package com.example.kiratest.test;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    public static class Node{
        int key;
        int value;
        Node pre;
        Node next;
        Node(int k,int v){
            key=k;
            value=v;
        }
    }

    private final int capacity;//容量
    private final Node dummy=new Node(0,0);

    private final Map<Integer,Node> keyToNode=new HashMap<>();


    public LRUCache(int capacity) {
        this.capacity=capacity;
        //初始化哨兵节点的指向
        dummy.pre=dummy;
        dummy.next=dummy;
    }

    //在链表头部添加一个节点(把一本书放到最上面)
    private void  pushFront(Node x){
        //改变抽出来的书的节点指向
        x.pre=dummy;
        x.next=dummy.next;

        //改变哨兵节点的指向
        x.pre.next=x;
        //让插入位置的节点的下一个节点的pre指向x
        x.next.pre=x;
    }
    //删除一个节点
    private void remove(Node x){
        x.pre.next=x.next;
        x.next.pre=x.pre;

    }

    //根据Key获取对应的节点,并将该节点移动到链表头部
    private Node getNode(int key){
        if(!keyToNode.containsKey((key))){
            return null;
        }

        Node node =keyToNode.get(key);
        //将这本书抽出来
        remove(node);
        //将这本书放到最上面
        pushFront(node);

        return node;
    }


    public int get(int key){

        Node node=getNode(key);
        return node!=null?node.value:-1;

    }

    public void put(int key,int value){
        Node node=getNode(key);
        if(node!=null){
            node.value=value;
            return;
        }

        node=new Node(key,value);
        keyToNode.put(key,node);

        //将这本书放到最上面
        pushFront(node);
        //书本个数超过容量,那我们就移除最后一本书
        if(keyToNode.size()>capacity){
            Node backNode=dummy.pre;
            keyToNode.remove(backNode.key);
            //移除掉最后一本书，也就是移除哨兵的上一本书
            remove(backNode);
        }


    }

}
